package 链表;

/**
 * [NO0设计链表]
 * 链表基础类
 *
 * @author yuank
 * @date 2025/1/16 9:39:18
 */

/**
 * 场景：到底迭代/指定迭代
 * ps 头变更问题 && size/index(越界问题) && 有size不推荐使用while进行迭代
 * 1 迭代操作执行依据是第2点
 *     >(理解错误)newHead = newHead.getNext(); 如果是屁股玩法newHead是虚拟头可以统一 如果newHead是head那么会错过head本身
 * 2 当需要对链表的结构进行变动的时候 添加/删除不保存前者 链表会无法连接起来  <<---------------------
 *     >屁股法可以留存 ->于是虚拟头让head也可以使用屁股法                                      |
 *     >如果指针反转情况 采取                                                              |
 * 结论 需要维持链表结构 思考需不需要前者或后者                                                |
 *      >前者可使用屁股 后者temp变量 然后再考虑如何迭代                                       |
 *                                                                                    |
 * while (Condition != null) // 123.4 //12 23 34  4                                   |
 *  (Condition.next != null) // 0.123 //01 12 13  3                                   |
 *   > Condition == null -> - ——, - ——, - —— ...; - =>会落在第一个null的位置,size +1     |
 *   >> 其实可以发现两种都会把元素遍历一遍 迭代次数是元素个数n 但是最后的落点是n+1                |
 *   >>> 操作对象既是迭代对象 然后遍历列表元素(相对)到底再往后.next一个                        |
 * 看场景 需要通过前者引用操作 或 本体即可操作(携带后者) ->->-------------------------------------
 */
class ListNode {
    private Integer value;
    private ListNode next;


    public static ListNode create(){
        return new ListNode(1,
                new ListNode(2,
                    new ListNode(3,
                        new ListNode(4,
                            new ListNode(5, null)))));
    }

    //
    public ListNode(Integer value, ListNode next) {
        this.value = value;
        this.next = next;
    }
    public ListNode() {
        this.create();
    }

    //get set
    public int getValue() { return value; }
    public ListNode getNext() { return next;}
    public void setValue(Integer value) { this.value = value;}
    public void setNext(ListNode next) { this.next = next;}
    public ListNode getSelf() { return this; }

    public void print(){
        System.out.print(value + ",");

        //正常迭代到底-校验元素既是当前
        while (next != null){
            System.out.print(next.value + ",");
            next = next.next;
        }
    }


    static class ForTest01{
        public static void main(String[] args) {
            ListNode listNode = new ListNode(null, null).create();
            listNode.deleteIndexFormBottom(listNode, 1);
            listNode.print();
        }
    }

    //[NO1 链表上去除元素]
    public ListNode deleteValue(ListNode head, int val) {
        if (head == null) { return null;}

        ListNode newHeadForReturn = new ListNode(null, head); //虚拟头
        ListNode newHeadForBottom = newHeadForReturn; //遍历头

        /**
         * 和指针时使用前一个数表示head 来处理开头元素一致
         * **/
        while (newHeadForBottom.next != null) {

/*          if (newHeadForBottom.next.getValue() == val) {
                //移除节点
                newHeadForBottom.setNext(newHeadForBottom.next.next);
            }
            PS: 1234 删2 会额外越过一个节点: 期望134-> 实际14
            newHeadForBottom = newHeadForBottom.next;*/

            //移除和向下 非此即彼
            if (newHeadForBottom.next.getValue() == val) {
                //移除节点
                newHeadForBottom.setNext(newHeadForBottom.next.next);
            } else {
                newHeadForBottom = newHeadForBottom.next;
            }
        }

        return newHeadForReturn.next;
    }

    //[NO3 反转链表]
    public ListNode reserveListNode(ListNode head){
        ListNode pre = null; //前者
        ListNode cur = head; //当前
        ListNode temp = null; //下一个

        /**
         * 一个是通过前者.next 保留了前者的引用 此通过一个temp满足了链表操作后的衔接性
         * **/
        while (cur != null) { // - ——, ...- ——;- ； 123.4 head开始 最终位置size.next 次数n
            //先留存下一个
            temp = cur.next;

            //操作当前往前指
            cur.next = pre;

            //向下
            pre = cur;
            cur = temp;

        }
        //return cur; 操作后默认向下 于是最后一个时已向下 cur=null
        return pre;
    }


    /**
     * [NO4] 链表两个节点交换
     *  [~] ->[-] ->[-] -> || [-]
     *      1     2     3
     *  三个指针的操作
     */
    public ListNode doubleChange(ListNode head){
        ListNode newStartHead = new ListNode(null, head); // 虚拟头
        ListNode operationNode = newStartHead;

        //迭代
        while (operationNode.next != null &&  // 对象.属性
                // 上是对下的校验 理解一下 属性/对象
                // PS:可以发现迭代对象就是目标对象 然后元素遍历到底后再next一个
                operationNode.next.next != null) { // 对象.(属性)(对象).属性


            //临时
            ListNode temp = operationNode.next.next.next;

            ListNode firstNode = operationNode.next;
            ListNode secondNode = operationNode.next.next;

            operationNode.next = secondNode;
            secondNode.next =firstNode;
            firstNode.next = temp;

            //下轮
            operationNode = firstNode; // 一去了二的位置 二是下一轮的虚拟头
        }

        return newStartHead.next; // 头发生变动
    }

    /**
     * [NO5] 删除倒数第n个元素
     * 两个距离n-1个元素的 两位指针 一个到底另外一个就是目标 -666
     * 123.4 到底为4
     * n=1删2: 13 ->24 3的位置是n+1
     * 选择while(node != null || node.next != null) ?
     */
    public boolean deleteIndexFormBottom(ListNode head, int IndexFormBottom) {

        ListNode newhead = new ListNode(null, head);
        ListNode tail = new ListNode(null, head);

        for (int i = 0; i <= IndexFormBottom; i++) { // n+1

            //删除位置大于长度
            if (newhead == null) { return false;}

            newhead = newhead.next;
        }
        //此时head的位置是 n+1

        //同步向下
        while (newhead.next != null) { // size +1
            newhead = newhead.next;
            tail = tail.next;
        }
        //此时tail的位置是目标 前一个

        //删除操作
        tail.next = tail.next.next;
        return true;
    }

    /**
     * [NO7] 两个链表相交 ps地址值
     * 脑子有图比啥都好使
     */
    public static ListNode twoNodeCoincide(ListNode head1, ListNode head2) {
        return null;
    }
}

public class ListNodes {
    private int size; // 维护独立存在的size
    private ListNode head; // 持有头就可以了

    //private ListNode[] head //(等价)链表和数组同为最底层结构

    public static ListNodes createNormal() {
        return new ListNodes(5, ListNode.create());
    }

    public ListNodes() {
    }

    public ListNodes(int size, ListNode head) {
        this.size = size;
        this.head = head;
    }

    public void print() {
        head.print();
    }

    static class ForTest2 { // 由于动态内部类是依附于外部的 所以不支持持有静态
        public static void main(String[] args) {
            //初始化结构
            ListNodes nodes = new ListNodes().createNormal();
        }
    }

    /**
     * [NO2设计链表]
     * <p>
     * get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
     * addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
     * addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
     * addAtIndex(index,val)：>在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。
     * >>如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
     * deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
     */
    public int getIndex(int index) {
        ListNode newHead = head;

        //size 处理越界问题
        if (index < 0 || index >= size) {
            return -1;
        }

        for (int i = 0; i <= index; i++) { // 完整
            newHead = newHead.getNext();
        }

        //newHead即是当前元素
        return newHead.getValue();
    }

    public void addAtHead(int value) {
        ListNode newHead = new ListNode(value, head);
        head = newHead;

        size++;
    }

    public void addAtTail(int value) {

        // size 处理head变更问题
        if (size == 0) {
            head = new ListNode(value, null);
            return;
        }

        //无需越界处理

        ListNode newHeadBottom = new ListNode(null, head); // 到底
        // ListNode newHeadHold = newHeadBottom; // 无需保留持有(头变更情况不存在了)

        //PS: 不推荐使用while迭代遍历 用if(size)迭代遍历比较统一 82行处是因为维护size字段 不支持if(size)

        //屁股法留有前者+head(无需处理head(题意tail))
        while (newHeadBottom.getNext() != null) {
            newHeadBottom = newHeadBottom.getNext();
        }

        //出现空说明当前元素是最后元素
        newHeadBottom.setNext(new ListNode(value, null));

        size++;
    }

    public void addAtIndex(int index, int value) {
        ListNode newHeadBottom = new ListNode(null, head); // 需要到底+要通过前一个操作(启用屁股玩法)

        //越界退出
        if (index < 0 || index > size) {
            return;
        }

        //head变更
        if (index == 0) {
            head = new ListNode(value, head);
            return;
        }

        //索引界限内
        for (int i = 0; i < index; i++) { // 少一次保证是插入元素前一个引用 方便链条变更
            newHeadBottom = newHeadBottom.getNext();
        }

        //此时 newHead 是索引处前一个元素引用

        //连接后面
        ListNode newListNode = new ListNode(value, newHeadBottom.getNext());
        //连接前面
        newHeadBottom.setNext(newListNode);

        size++;
    }

    public void deleteAtIndex(int index) {

        //越界退出
        if (index < 0 || index >= size) {
            return;
        }

        //head变更
        if (index == 0) {
            head = head.getNext();
        }

        //常规情况
        ListNode newHeadBottom = new ListNode(null, head);

        for (int i = 0; i < index; i++) { // 少一次保证是插入元素前一个引用 方便链条变更
            newHeadBottom = newHeadBottom.getNext();
        }

        // 此时是目标节点前一个

        //删除目标元素
        newHeadBottom.setNext(newHeadBottom.getNext().getNext());

        size--;
    }

}



